Recently, some remarkable progress has been made in image data compression techniques. The goal of these techniques is to raise the efficiency of, for example, digital transmission and recording by encoding the image data at a lower bit rate than would be required for unencoded image data. Exemplary techniques which have been used to obtain these coding efficiencies are predictive coding and transform coding.
In addition, further image data compression can be achieved by performing variable length encoding on the compressed code. The variable length encoding consists of varying the encoded bit width in accordance with the frequency of occurrence of the value to be encoded. Thus, a smaller bit rate can be obtained as compared to fixed length coding. One example of a variable length code is a Huffman code.
Next, as an example of variable length coding, a description is given with reference to FIGS. 7a and 7b of a method for generating Huffman codes. Assume that the fixed length data values S.sub.1 S.sub.1, . . . S.sub.t are to be converted into Huffman codes. FIGS. 7a and 7b show an example for the case where t=6. First of all, codes S.sub.1 to S.sub.6 are arranged in order of the magnitude of the frequency of their occurrence (these magnitudes can be normalized to obtain the probabilities of occurrence). The probabilities of occurrence of codes S.sub.1 to S.sub.6 are respectively 0.35, 0.20, 0.15, 0.15, 0.10 and 0.05 as shown in FIG. 7a. They are therefore arranged in order of codes S.sub.1 to S.sub.6. Next, taking the two codes which have the smallest probability of occurrence as one group, their composite probability (the sum of the two probabilities of occurrence) is found.
In FIG. 7a, codes S.sub.6 and S.sub.5 have the smallest probability of occurrence, and their composite probability is 0.15. Next, this group and the other codes are arranged in order of magnitude of their probabilities of occurrence for composite probability. The two codes (or groups) having the smallest probability of occurrence (or composite probability) are taken as a new group, and the composite probability of this group is found. Subsequently, this process is repeated until a listing with the composite probability of one has been effected as shown in FIG. 7a.
Next, using FIG. 7a, a code tree as shown in FIG. 7b is compiled. "0" and "1" are then allocated in accordance with the branching of this code tree. In FIG. 7b, the upper branches are allocated "0", while the lower branches are allocated "1". The Huffman codes are obtained by following this branching. For example, as shown by the thick line in FIG. 7b, the fixed length code S.sub.4 passes along a branch "0", along a branch "1", and finally along a branch "0", so it is converted to the Huffman code "010". The Huffman codes of the codes S.sub.1 to S.sub.6 found in this way are shown in Table one below.
TABLE 1 ______________________________________ CODE Huffman Code ______________________________________ S.sub.1 00 S.sub.2 10 S.sub.3 11 S.sub.4 010 S.sub.5 0110 S.sub.6 0111 ______________________________________
As shown in Table one, codes which have high probability of occurrence are converted into Huffman codes of short bit length, while codes which have a low probability of occurrence are converted into Huffman codes of longer bit length. In this way, the overall bit rate for transmitting a given number of data values can be reduced.
In general, to decode such variable length code into fixed length code, a conversion table, embedded in a solid state memory such as a ROM, is used. In FIG. 7a, for convenience in explanation, the maximum bit number of the variable length code (Huffman code) was taken as being four bits, in an actual image data signal, the maximum bit number may be larger, for example, 17 bits.
For example, one prior art method for decoding the variable length is shown in FIG. 11. A n-bit parallel data signal is coupled to a look-up table (LUT) 111. The n-bit signal contains a variable length code word which is used as an address for data stored in LUT 111. The variable length code may be n bits in length. The data stored in LUT 111 corresponds to the code length and the code value. The code length data specifies the length of the variable length code word that has been identified in the n-bit signal. The code value is the decoded (i.e. fixed length) value of the variable length code. The output of LUT 111 is code length and code value which are z-bit and v-bit parallel data streams respectively.
In operation, the variable length code received in the n-bit signal is used as an address to a memory location in LUT 111. After the memory location has been identified, the LUT outputs code length and code value which are stored at the memory location.
However, the prior art device of FIG. 11 requires a large memory because an n-bit address must be provided as an input to LUT 111. In addition, each memory location in LUT 111 stores an z-bit code length and a v bit code value. As a result, a total of z+v bits are needed to store code length and the code value. The total number of bits required for LUT one is 2.sup.n *(z+v).
Accordingly, proposals have been made to limit the size of the conversion tables to reduce the required memory size for the conversion table. However, these techniques have resulted in a slower decoding process.
For example, one such apparatus was proposed in U.S. Pat. No. 5,138,316, entitled VARIABLE LENGTH CODE DEMODULATING APPARATUS AND ADDRESS CONTROL METHOD THEREOF, issued to Konishi (hereinafter '316 patent), shown in FIG. 10 and incorporated herein by reference for its teachings on decoders for variable length codes. The '316 patent describes a variable length code in which the most significant bits (MSBs) are provided to conversion table 822 and where the least significant bits (LSBs) are provided to conversion table 823. Respective 9 bit output values of each conversion table 822, 823 are coupled to a selector 830. In addition, a five bit output value of conversion table 822 is coupled to the LSB input of conversion table 823. Also a one bit output signal is provided by conversion table 822 to selector 824.
In operation, 15 parallel bits of a variable length encoded bit stream are applied through the input terminal 821. The most significant eight bits of a segment of the bit stream are applied to conversion table 822. The seven least significant bits are provided at the address input terminal of conversion table 823 as the LSBs of a 12 bit address value which also include the 5-bit conversion code from conversion table 822. If a Variable length Code (VLC) value consists of 8 bits or less, then a length code "1" is produced by conversion table 822 to the control terminal 826 of selector 824. Further, the 9-bit fixed length value stored at the address indicated by this variable length code value is provided by conversion table 822 to the first input terminal 828 of the selector 824. Since the selector receives a "1" at its control input terminal 826, it passes the fixed length code applied to the first input terminal 828.
In contrast, if the variable length code value is 9 bits or more, a length code "0" is generated by the conversion table 822. The conversion table 822 also generates the 5-bit conversion code stored at the address corresponding to the most significant 8 bits. Thus, a 12-bit code word is supplied to the address input port of conversion table 823. The address conversion table 823 is thus designated and the 9-bit fixed length code corresponding to the VLC of 9-bits or more is applied to the second input terminal 830 of selector 824.
Although this arrangement reduces the table size, it also reduces the rate at which the VLC can be decoded. This occurs because conversion table 822 first attempts to decode the VLC. However, if conversion table 822 fails to decode the VLC, conversion table 822 must first provide additional bits to conversion table 823 prior to decoding by conversion table 823.